

# 377. 组合总和 Ⅳ


def combinationSum4(nums, target):
    dp = [[None] * (target + 1) for _ in range(len(nums) + 1)]
    for i in range(0, len(nums) + 1):
        dp[i][0] = 1
    for i in range(1, target + 1):
        if nums[0] == i:
            dp[0][i] = 1
        else:
            dp[0][i] = 0
    for i in range(1, len(nums) + 1):
        for j in range(1, target + 1):
            if j < nums[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i - 1]]
    print(dp)
    return dp[len(nums)][target]

if __name__ == "__main__":
    nums = [3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25]
    target = 10
    combinationSum4(nums,target)